\documentclass{acm_proc_article-sp}
\usepackage{color}
\usepackage[utf8]{inputenc}
\usepackage{moreverb}
\usepackage{fancybox}
\usepackage{graphicx}

\def\inputfig#1{\input #1}
\def\inputtex#1{\input #1}
\def\inputal#1{\input #1}
\def\inputcode#1{\input #1}

\inputtex{logos.tex}
\inputtex{refmacros.tex}
\inputtex{other-macros.tex}

\begin{document}
\title{Processing List Elements in Reverse Order}
\numberofauthors{1}
\author{\alignauthor
Irène Durand and Robert Strandh\\
\affaddr{University of Bordeaux}\\
\affaddr{Science and Technology College}\\
\affaddr{LaBRI, 351, Cours de la Libération}\\
\affaddr{33405 Talence Cedex, France}\\
\email{robert.strandh@u-bordeaux.fr}
\email{irene.durand@u-bordeaux.fr}}

\toappear{Permission to make digital or hard copies of all or part of
  this work for personal or classroom use is granted without fee
  provided that copies are not made or distributed for profit or
  commercial advantage and that copies bear this notice and the full
  citation on the first page. Copyrights for components of this work
  owned by others than the author(s) must be honored. Abstracting with
  credit is permitted. To copy otherwise, or republish, to post on
  servers or to redistribute to lists, requires prior specific
  permission and/or a fee.

 ELS '15, April 20 - 21 2015, London, UK
 Copyright is held by the authors.
%  ACM 978-1-4503-2931-6/14/08\$15.00.???
%  http://dx.doi.org/10.1145/2635648.2635656
}

\maketitle

\begin{abstract}
The \commonlisp{} sequence functions and some other functions such as
\texttt{reduce} accept a keyword parameter called \texttt{from-end}.
In the case of \texttt{count} and \texttt{reduce}, when the value of
that parameter is \emph{true}, it is required that the elements are
processed in reverse order.  Some implementations, in particular
\sbcl{}, \ccl{}, and \lispworks{}, implement the reverse-order
traversal of a list by non-destructively reversing the list and then
traversing the reversed version instead.  This technique requires
$O(n)$ additional heap space (where $n$ is the length of the list),
and increases the amount of work required by the garbage collector.

In this paper, we present a technique that only uses additional
\emph{stack space}.  To avoid stack overflow, our technique traverses
parts of the list multiple times when the list has more elements than
the available stack space can handle.  We show that our technique is
fast, in particular for lists with a large number of elements, which
is also the case where it is the most important to avoid allocating
heap space.
\end{abstract}

\category{D.3.4}{Programming Languages}{Processors}
[Code generation, Run-time environments]

\terms{Algorithms, Languages}

\keywords{\commonlisp{}, List processing}

\inputtex{sec-introduction.tex}
\inputtex{sec-previous.tex}
\inputtex{sec-our-method.tex}
\inputtex{sec-benchmarks.tex}
\inputtex{sec-conclusions.tex}
\inputtex{sec-acknowledgments.tex}
\pagebreak
\inputtex{sec-appendix.tex}

\bibliographystyle{abbrv}
\bibliography{reverse-order}
\end{document}

%%  LocalWords:  sandboxing runtime
